package com.huangyi;

public class Main {
    public static void main(String[] args) {
        //重排链表
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode() {}
         *     ListNode(int val) { this.val = val; }
         *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
         * }
         */
        class Solution {
            public void reorderList(ListNode head) {
                // 0) 早退：空链或单节点，无需处理
                if (head == null || head.next == null) return;

                // 1) 快慢指针找“左中点” slow
                ListNode slow = head, fast = head;
                while (fast.next != null && fast.next.next != null) {
                    slow = slow.next;
                    fast = fast.next.next;
                }

                // 2) 断开并反转后半段
                ListNode second = slow.next;
                slow.next = null;                 // 断开前半尾
                second = reverse(second);         // 原地反转后半

                // 3) 交替合并：前半(head)与后半(second, 已反转)
                ListNode p1 = head, p2 = second;
                while (p2 != null) {
                    ListNode n1 = p1.next, n2 = p2.next; // 先保存后继，避免断路
                    p1.next = p2;
                    p2.next = n1;
                    p1 = n1;
                    p2 = n2;
                }
                // 就地修改，void 无需返回
            }

            // 三指针原地反转
            private ListNode reverse(ListNode head) {
                ListNode prev = null, curr = head;
                while (curr != null) {
                    ListNode next = curr.next; // 保存旧路口
                    curr.next = prev;          // 反转指向
                    prev = curr;               // prev 前进
                    curr = next;               // curr 走向旧路口
                }
                return prev; // 新头
            }
        }


        //合并 K 个升序链表
        /**
         * Definition for singly-linked list.
         * public class ListNode {
         *     int val;
         *     ListNode next;
         *     ListNode() {}
         *     ListNode(int val) { this.val = val; }
         *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
         * }
         */
        class Solution2 {
            public ListNode mergeKLists(ListNode[] lists) {
                if (lists == null || lists.length == 0) return null;
                return mergeRange(lists, 0, lists.length - 1);
            }

            private ListNode mergeRange(ListNode[] lists, int l, int r) {
                if (l == r) return lists[l];                 // 可能为 null，无妨
                int m = l + (r - l) / 2;
                ListNode a = mergeRange(lists, l, m);
                ListNode b = mergeRange(lists, m + 1, r);
                return mergeTwo(a, b);
            }

            private ListNode mergeTwo(ListNode a, ListNode b) {
                ListNode dummy = new ListNode(0);
                ListNode tail  = dummy;
                while (a != null && b != null) {
                    if (a.val <= b.val) {
                        tail.next = a; a = a.next;
                    } else {
                        tail.next = b; b = b.next;
                    }
                    tail = tail.next;
                }
                tail.next = (a != null) ? a : b;             // 一次性挂尾
                return dummy.next;
            }
        }

    }
}